package top.whk0710.algorithms.sort;

import java.util.Arrays;

public class MyHeapSort {

	public static void main(String[] args) {
		int[] array = {8,3,2,4,5,1,6,7};
		//Util.printArrays(array, 4);
		
		sort(array);
		
		System.out.println(Arrays.toString(array));
	}
	
	public static void sort(int[] arr){
		for(int i=arr.length/2-1;i>=0;i--){
			adjust(arr,i,arr.length);
		}
		
		for(int i=arr.length-1;i>0;i--){
			int tmp = arr[0];
			arr[0] = arr[i];
			arr[i] = tmp;
			adjust(arr,0,i);
		}
	}
	
	public static void adjust(int[] arr, int i, int length){
		
		int tmp  = arr[i];
		
		for(int k = 2 * i + 1; k < length; k = k * 2 + 1){
			if(k + 1 < length && arr[k+1] > arr[k]) k++;
			if(arr[k] > tmp){
				arr[i] = arr[k];
				i = k;
			}else{
				break;
			}
		}
		
		arr[i] = tmp;
	}
}
